package com.leetcode.algs4.graph.mst;

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @author Dennis Li
 * @date 2020/6/18 19:58
 */
public class KruskalMST {
    private final Queue<Edge> mst;

    public KruskalMST(EdgeWeightGraph G) {
        mst = new LinkedList<>();

        PriorityQueue<Edge> pq = new PriorityQueue<>();

        // 将G的所有边加入优先队列
        G.edges().forEach(pq::offer);

        // 创建一个并查集用于辅助
        UF uf = new UF(G.V());

        while (!pq.isEmpty() && mst.size() < G.V() - 1) {
            Edge edge = pq.poll();
            int v = edge.either(), w = edge.other(v);
            // 注意并查集的使用 -- 加强
            if (uf.connected(v, w)) continue; // 忽略失效的边
            // 合并分量
            uf.union(v, w);
            mst.offer(edge);
        }
    }

    public Iterable<Edge> edges() {
        return mst;
    }
}
